class Solution {
public:
    int ret = 0;
    int num;
    bool check[16];
    int pathNum = 0;

    int countArrangement(int n) {
        num = n;
        dfs();
        return ret;
    }

    void dfs()
    {
        if (pathNum == num)
        {
            ret++;
            return;
        }

        for (int i = 1; i <= num; i++)
        {
            if (!check[i] && ((pathNum + 1) % i == 0 || i % (pathNum + 1) == 0))
            {
                pathNum++;
                check[i] = true;
                dfs();
                pathNum--;
                check[i] = false;
            }
        }
    }
};